【思维迷宫】2的n次方能包含所有十进制序列吗？（算法测试）

程序思维 2019年7月28日

我为此自己写了一段代码进行测试

[python]
import time
def find(num):
    head = 0
    while True:
        if str(num) in str(2 ** head):
            return head
        head += 1
num = 0
f = open('test.txt','w')
for _ in range(0,599999):
    timestart = time.time()
    finalnum = find(num)
    finaltime = time.time()-timestart
    print("[",finaltime,"]",num,"in",finalnum,"with",2**finalnum)
    f.writelines(['\n',str(num)," in ",str(finalnum)," ",str(2**finalnum)])
    num += 1
[python]

用这个程序会遍历一遍从0~599999所有数字在2的n次方（从n=0开始，依次递增1查找，n ∈ N）第一次出现的情况

会生成一个文件大约358MB的文件

程序无法彻底证明这个东西，但是可以初步看到结果，为此特地转发一篇文章供大家查看。

转载于知乎，原帖地址

答案是：能！

严格的表述是这样的：

定理 [公式] ：对于由 [公式] 组成的任意有限序列 [公式] ，存在自然数 [公式] 使得 [公式] 的十进制表示包含序列 [公式] 。

比如 [公式] =“ [公式] ”，取 [公式] ，此时：

[公式]

直接看定理 [公式] ，感觉证明起来必定很难，涉及到 [公式] 的幂的各个十进制位数，然而这不过是个小把戏，实际上定理 [公式] 只是一个更强的定理的一个推论，直接证明这个更强的定理，会简单很多。

定理 [公式] ：在十进制表示下，对任意的正整数 [公式] ，存在自然数 [公式] 使得 [公式] 以 [公式] 的各位数开头。

比如 [公式] ，取 [公式] ，有 [公式] 以 [公式] 开头。

如果序列 [公式] 不是以 [公式] 开头，那么可以把它看成是一个十进制正整数，应用定理 [公式] 即得定理 [公式] 成立；如果 [公式] 以 [公式] 开头，则不能简单看作十进制正整数，不过可以在 [公式] 开头添加 [公式] ，再使用定理 [公式] 就可以证明定理 [公式] 了。所以接下来要做的是证明定理 [公式] 。

如果定理 [公式] 确实成立，那么肯定存在自然数 [公式] 使得： [公式] 也就是说，这不单是要寻找合适的 [公式] ，还要寻找合适的 [公式] 。不过，利用一些技巧可以避开这个 [公式] 的阻挠。注意到 [公式] 式是幂的形式，但是如果取一下对数呢？取对数是降级运算，可以将乘除变换为加减，问题就简单很多了。不过在取对数之前，先将 [公式] 表示成科学计数法的形式，例如 [公式] 。我们设 [公式] ，其中 [公式] 。这个时候 [公式] 式就成了： [公式] 在不等式上取以 [公式] 为底的对数可得： [公式]

到了这里，还是出现 [公式] 啊，怎么就“避开这个 [公式] 的阻挠”了呢？别急，我们还差一步。如果我们在这个式子里边忽视掉整数部分：因为 [公式] ，那么 [公式] ，也有 [公式] ，并且 [公式] 是个很小的数，也就是 [公式] 和 [公式] 相差很少，且它们都不大于 [公式] 。如果我们只取 [公式] 式的小数部分，由于 [公式] 和 [公式] 相差的值很小，且都不大于 [公式] ，那么取了小数部分之后不等式还是成立的——只有一种特殊情况：当 [公式] 时，这个时候取小数部分的话就变成 [公式] 了，就会小于 [公式] 了，这个情况下我们仍保留 [公式] 这部分，就可以保证不等式成立。

定义 [公式] 为取 [公式] 的小数部分，比如 [公式] ， [公式] ，取[公式] 式各项的小数部分可得： [公式]

这时候终于摆脱 [公式] 了。现在我们也不用考虑 [公式] 的整数部分，对每一个自然数 [公式] ， [公式] 都产生一个小数部分，也就相当于在区间 [公式] 上画一点。这么多个 [公式] ，肯定有某些点会出现在区间 [公式] 上吧？只要有某些点出现在这个区间上， [公式] 的解就找到了。

下面的步骤就是一些技巧了。

取正整数 [公式] ，也就是 [公式] ，将区间 [公式] 等分成 [公式] 个小区间，每个的长度都是 [公式] 。让 [公式] 取 [公式] 一共 [公式] 个自然数值，那么就会有 [公式] 个 [公式] 的值，根据鸽巢原理，这些值中最起码有两个处于同一个小区间，换言之，存在 [公式] 使得：[公式] 但是， [公式] 会不会等于 [公式] 呢？如果它等于 [公式] ，那么 [公式] 就是个整数，这和 [公式] 是无理数矛盾。所以 [公式] 。令 [公式] ，就得到 [公式] 。注意 [公式] 小于区间 [公式] 的长度，所以从任一个 [公式] 出发，不断地加 [公式] ，因为每加一次 [公式] ，小数部分就向前增一点点，并且增量小于区间 [公式] 的长度，所以必会使得小数部分进入区间 [公式] 内。

再回到开头，要使 [公式] 的十进制表示开头出现 [公式] ，最起码必要求 [公式] ，于是 [公式] 。我们就让自然数 [公式] ，然后从 [公式] 出发不断地加 [公式] ，根据上一段的讨论，必会有某个 [公式] 使得 [公式] 进入区间 [公式] 内，亦即这个 [公式] 满足 [公式] 式。

此时，根据 [公式] 式逆向推导，因为取的是以 [公式] 为底的对数，取小数部分而省去的整数如果补回来后也不过相当于乘以 [公式] 的幂，所以最后 [公式] 的十进制表示的开头就是 [公式] 了。定理 [公式] 证毕。

如果仔细分析就会发现，这个定理之所以成立，很大程度取决于 [公式] 是无理数，而非 [公式] 次幂或者十进制的特殊性。所以，把证明方法稍微改一下，就可以证明：

定理 [公式] ：如果 [公式] 为无理数，在 [公式] 进制表示下，对任意正整数 [公式] ，存在自然数 [公式] 使得 [公式] 以 [公式] 的各位数开头。

同样有相应形式的定理 [公式] 。


转载于知乎，原帖地址

You may also like...